package LRU;

import java.util.HashMap;
import java.util.Map;

//自己实现LRU
public class MyLRUCache {

    //构建一个Node节点，作为数据载体
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;
        Node<K,V> pre;
        public  Node(){
            this.next=null;
            this.pre=null;
        }
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next=null;
            this.pre=null;
        }
    }
    //构造一个虚拟的双向链表，存放Node
    class DoubleLinkedList<K,V>{
        Node<K,V> head;
        Node<K,V> tail;
        //构造方法
        public DoubleLinkedList() {
            head= new Node<>();
            tail= new Node<>();
            head.next=tail;
            tail.pre=head;
        }
        //添加到头
        public  void addHead(Node<K,V> node){
            node.next=head.next;
            node.pre=head;
            head.next.pre=node;
            head.next=node;
        }
        //删除
        public void removeNode(Node<K,V> node){
            node.next.pre=node.pre;
            node.pre.next=node.next;
            node.pre=null;
            node.next=null;
        }
        //获得最后一个节点
        public  Node getLast(){
            Node node= tail.pre;
            return node;
        }

    }
    private  int cacheSize;
    Map<Integer,Node<Integer,Integer>> map;
    DoubleLinkedList<Integer,Integer> doubleLinkedList;

    public MyLRUCache(int cacheSize) {
        this.cacheSize=cacheSize;
        map=new HashMap<>();
        doubleLinkedList=new DoubleLinkedList<>();
    }

    public  int get(int key){
        if(!map.containsKey(key)) return -1;
        Node<Integer,Integer> node=map.get(key);
        doubleLinkedList.removeNode(node);
        doubleLinkedList.addHead(node);
        return node.value;
    }

    public  void put(int key,int value){
        //如果已经存在，更新，并移至队头
        if(map.containsKey(key)){
            Node<Integer,Integer> node=map.get(key);
            node.value=value;
            doubleLinkedList.removeNode(node);
            doubleLinkedList.addHead(node);
        }else{
            //如果满了，删除队尾
            if(map.size()==cacheSize){
                Node<Integer,Integer> lastNode = doubleLinkedList.getLast();
                map.remove(lastNode.key);
                doubleLinkedList.removeNode(lastNode);
            }
            Node<Integer, Integer> newNode = new Node<>(key,value);
            map.put(key,newNode);
            doubleLinkedList.addHead(newNode);
        }


    }


    public static void main(String[] args) {
        MyLRUCache myLRUCache = new MyLRUCache(3);
        myLRUCache.put(1,1);
        myLRUCache.put(2,2);
        myLRUCache.put(3,3);

        System.out.println(myLRUCache.map.keySet());
        myLRUCache.put(1,1);
        myLRUCache.put(4,3);
        System.out.println(myLRUCache.map.keySet());
    }

}
